package datastructure.sort;

import java.util.Comparator;

/**
 * Description：希尔排序
 * Author: zhangc
 * Date：2017/7/23 13:33
 */
public class SheelSort {

    public static <T extends Comparable<? super T>> void shellSort(T[] array) {
        int d = array.length;//间隔距离
        while (d != 0) {
            d = d >> 1;
            for (int i = 0; i < d; i++) {
                for (int j = i + d; j < array.length; j += d) {
                    int x = j - d;
                    T temp = array[ j ];
                    for (; x >= 0 && temp.compareTo(array[ x ]) < 0; x -= d) {
                        array[ x + d ] = array[ x ];
                    }
                    array[ x + d ] = temp;
                }
            }
        }
    }

    public static <T> void shellSort(T[] array, Comparator<? super T> comparator) {
        int d = array.length;
        while (d != 0) {
            d = d >> 1;
            for (int i = 0; i < d; i++) {
                for (int j = i + d; j < array.length; j += d) {
                    int x = j - d;
                    T temp = array[ j ];
                    for (; x >= 0 && comparator.compare(temp, array[ x ]) < 0; x -= d) {
                        array[ x + d ] = array[ x ];
                    }
                    array[ x + d ] = temp;
                }
            }
        }
    }


}
